1. Field of the Invention
The present invention relates to computer networks and more particularly to avoiding Internet Protocol (IP) lookup with Multipoint-to-Multipoint (MP2MP) Label Switched Paths (LSPs) in a computer network.
2. Background Information
A computer network is a geographically distributed collection of nodes interconnected by communication links and segments for transporting data between end nodes, such as personal computers and workstations. Many types of networks are available, with the types ranging from local area networks (LANs) to wide area networks (WANs). LANs typically connect the nodes over dedicated private communications links located in the same general physical location, such as a building or campus. WANs, on the other hand, typically connect geographically dispersed nodes over long-distance communications links, such as common carrier telephone lines, optical lightpaths, synchronous optical networks (SONET), or synchronous digital hierarchy (SDH) links. The Internet is an example of a WAN that connects disparate networks throughout the world, providing global communication between nodes on various networks. The nodes typically communicate over the network by exchanging discrete frames or packets of data according to predefined protocols, such as the Transmission Control Protocol/Internet Protocol (TCP/IP). In this context, a protocol consists of a set of rules defining how the nodes interact with each other.
The data packets transferred among the network nodes may include fixed-sized data cells and/or variable-sized data frames. Each data packet typically comprises “payload” data prepended (“encapsulated”) by at least one network header formatted in accordance with a network communication protocol. The network headers include information that enables the client nodes and intermediate network nodes, such as routers, to route the packet efficiently through the computer network. Often, a packet's network headers include at least a data-link (layer 2) header and an internetwork (layer 3) header, as defined by the Open Systems Interconnection (OSI) Reference Model. The OSI Reference Model is generally described in more detail in Section 1.1 of the reference book entitled Interconnections Second Edition, by Radia Perlman, published September 1999, which is hereby incorporated by reference as though fully set forth herein.
In operation, a network node may send a data packet to a network interface of an intermediate network node. Thereafter, the intermediate network node receives the packet and forwards the packet to its next destination. For example, the intermediate is network node may perform a layer-2 switching function that simply re-directs the packet from one network interface to another based on the contents of the packet's data-link header. Alternatively, the intermediate network node may perform a layer-3 routing function, or forwarding decision, that selects the most appropriate network interface to forward the packet based on the contents of the packet's internetwork header.
A source node (sender) may be configured to transfer a unidirectional stream of data packets, or a “data flow,” to a destination node (receiver) in a data network. The data stream is unidirectional in that data travels one-way from the sender to the receiver. The logical procession of intermediate network nodes that transmit and receive data packets from the sender to the receiver defines the data stream's data path. A first node that is nearer the receiver in the data stream's data path than a second node in the stream is said to be “downstream” from the second node. Likewise, a first node that is nearer the sender in the data stream's path than a second node in the stream is said to be “upstream” from the second node.
“Unicast” data transfer (i.e., unicast forwarding) involves forwarding a data packet from a single process of an end node (“source”) to a single process of an end node (“receiver”) on the computer network. Often the destination of the data packet issued by a source may be more than one, but less than all of the receivers on the network. This type of “multicast” data transfer (i.e., multicast forwarding) is typically employed to segregate communication between groups of receivers on the network. IP multicasting, in particular, may be used to disseminate data to a large group of receivers on the network.
To effect IP multicasting, the source generally specifies a destination IP address that is a multicast group address for the message and, as such, can only represent receivers of packets. The IPv4 (or IPv6) address range is subdivided into different prefixes, one of which is designated for use by IP multicast. Receivers typically notify their communication software of their desire to receive messages destined for the multicast group address; this is called “joining a multicast group.” These receiving members then “listen” on the multicast address and, when a multicast message is received at a receiver, it delivers a copy of the message to each process that belongs to the group.
IP multicasting relies on (i) a group management protocol to establish and maintain local multicast group membership, and (ii) multicast routing protocols to route packets efficiently, such as, e.g., Protocol Independent Multicast (PIM). The Internet Group Management Protocol (IGMP) manages packet communication between end nodes, e.g., hosts, and their local intermediate network node, e.g., multicast router, letting them join or leave groups. That is, IGMP is used to send a group membership message from a host to its directly connected router, indicating that the host wants to join a group (address) as a receiver. Note that IGMP is an IPv4 group membership protocol; the conventional Multicast Listener Discovery (MLD) protocol is substantially similar to, and performs the same functions as, IGMP, but for IPv6. When group membership is established, multicast packets (identified by a multicast source (S) and group (G) address in the destination address field of an IP header, or an “(S,G)” address) are forwarded between routers using multicast routing protocols. IGMP is described in RFC 3376, entitled Internet Group Management Protocol, Version 3, by Cain et al., October 2002, the contents of which are hereby incorporated by reference as though fully set forth herein.
In certain IP multicast networks, a single node or router acts as a meeting place for sources and receivers of multicast data. In other words, IP multicast packets from an upstream source and join messages from downstream routers “rendezvous” at this core router, or “Rendezvous Point” (RP). An RP may be configured to know the sources (S) for all multicast groups (G) of the IP multicast network. That is, by using an RP, other routers of the IP multicast networks are not required to know the addresses of the sources or every multicast group, but instead only the address of the RP. When a router (an end point) learns that an interested receiver wishes to join a particular group, the router will attempt to join the group at the RP, not to the actual source of the content. Thus, rather than the (S,G) notation above, the RP model utilizes a “(*,G)” notation, in which any source (*) may be used for a given group (G), i.e., multiple sources may source multicast traffic for the same group. The use of RPs and multicasting generally is further described in RFC 2362, entitled Protocol Independent Multicast-Sparse Mode (PIM-SM): Protocol Specification, by Estrin et al., June 1998, and in the Internet Draft by Fenner et al., entitled Protocol Independent Multicast-Sparse Mode (PIM-SM): Protocol Specification (Revised) <draft-ietf-pim-sm-v2-new-12.txt>, Internet Draft, March 2006, the contents of both which are hereby incorporated by reference as though fully set forth herein.
RPs for an IP multicast network may be determined using either manual configuration (e.g., a system administrator manually configures the RP at each router), or dynamic configuration. One example of a dynamically configured RP is an “Auto-RP” protocol (a proprietary protocol of Cisco Systems, Inc.), which automatically distributes information to routers that identifies the RP address for various multicast groups. Specifically, potential RPs announce themselves to a “mapping agent,” which resolves any conflicts from the potential RPs. The mapping agent then sends out the multicast group RP mapping information to the other routers, which are listening for this RP information (e.g., using pre-configured group addresses). Alternatively, a non-proprietary dynamic RP configuration method involves the use of a “bootstrap router” (BSR), which operates in a similar manner to the mapping agent of Auto-RP. In particular, a single BSR may be selected based on one or more configured policies. Potential RP candidates may announce themselves to the BSR, which then elects the RP based on the candidates. The use of a BSR is further described in the Internet Draft by Bhaskar et al., entitled Bootstrap Router (BSR) Mechanism for PIM <draft-ietf-pim-sm-bsr-09.txt>, Internet Draft, June 2006, the contents of which are hereby incorporated by reference as though fully set forth herein.
A virtual circuit may be used to define a logical end-to-end data path between two or more network nodes (e.g., participating in virtual private network, “VPN”). The virtual circuit may be established using, for example, conventional layer-2 Frame Relay (FR) or Asynchronous Transfer Mode (ATM) networks. Alternatively, the virtual circuit may “tunnel” data between its logical end points using known layer-2 and/or layer-3 tunneling protocols, such as the Layer-2 Tunneling Protocol (L2TP) and the Generic Routing Encapsulation (GRE) protocol. In this case, one or more tunnel headers are prepended to a data packet to appropriately route the packet along the virtual circuit. The Multi-Protocol Label Switching (MPLS) protocol may be used as a tunneling mechanism for establishing layer-2 virtual circuits or layer-3 network-based VPNs through an IP network. Notably, when the two or more nodes are located in different routing domains, devices in a plurality of interconnected routing domains may cooperate to establish the nodes' virtual circuit.
MPLS enables network nodes to forward packets along predetermined “label switched paths” (LSPs). Each LSP defines a logical data path, or virtual circuit, between a pair of source and destination nodes; the set of network nodes situated along the LSP may be determined using reachability information provided by conventional interior gateway protocols, such as OSPF, IS-IS, etc. Unlike traditional IP routing, where node-to-node (“next hop”) forwarding decisions are performed based on destination IP addresses, MPLS-configured nodes instead forward data packets based on “label” values (or “tag” values) added to the IP packets. As such, an MPLS-configured node can perform a label-lookup operation to determine a packet's next-hop destination. MPLS Traffic Engineering (TE) provides additional advantages over IP-based routing, such as enabling MPLS-configured nodes to reserve network resources, such as bandwidth, to ensure a desired quality of service (QoS).
Each destination represented via an LSP is associated with a locally allocated label value at each hop of the LSP, such that the locally allocated label value is carried by data packets forwarded over its associated hop. The MPLS label values are typically distributed among the LSP's nodes using, e.g., the Label Distribution Protocol (LDP), Resource Reservation Protocol (RSVP) or Multiprotocol (MP)-BGP protocol. Operationally, when a data packet is received at an MPLS-configured node, the node extracts the packet's transported label value, e.g., stored at a known location in the packet's encapsulating headers. The extracted label value is used to identify the next network node to forward the packet. Typically, an IGP label determines the packet's next hop within a routing domain, and a VPN label determines the packet's next hop across routing domains. More generally, the IGP label may be an MPLS label or any other encapsulation header used to identify the packet's next hop in the routing domain.
The packet may contain a “stack” of labels such that the stack's top-most label (i.e., an “outer-label”) determines the packet's next-hop destination. After receiving the packet, the MPLS-configured node “pops” (removes) the packet's top-most label from the label stack and performs a label-lookup operation to determine the packet's next-hop destination. Then, the node “pushes” (inserts) a new label value associated with the packet's next hop onto the top of the stack and forwards the packet to its next destination. This process is repeated for every logical hop along the LSP until the packet reaches its destination node. The above-described MPLS operation is described in more detail in Chapter 7 of the reference book entitled IP Switching and Routing Essentials, by Stephen Thomas, published 2002, which is hereby incorporated by reference as though fully set forth herein.
LSPs may be used to carry traffic from multiple IP streams that are demultiplexed at downstream end nodes of the LSP. A receiving end node (i.e., the destination of the LSP) receives the traffic, and may perform an “IP lookup” operation, e.g., into a forwarding/routing table, to determine where to forward the traffic based on the destination address of the traffic previously encapsulated in the LSP. The end node may then forward the traffic to the appropriate destination (i.e., without the LSP labels). Because an IP lookup may consume time and/or resources, an efficient advance has been made to utilize an “inner-label” that corresponds to a particular IP stream. Specifically, an upstream source of a particular IP stream on the LSP (e.g., an end/root node) may allocate a specific inner-label that corresponds to the particular IP stream. A receiving LSP end node may then use the inner-label to determine to which IP stream the received data belongs. By doing so, the receiving LSP end node may forward the traffic to an appropriate destination (or destinations) accordingly without the need for an IP lookup. Notably, the inner-label may be based on a context provided by the outer-label for the LSP if multiple LSPs end at the receiving end node, as will be understood by those skilled in the art.
Conventional LSPs are established between a source end node and a destination end node, i.e., “point-to-point” (P2P) LSPs. Multipoint LSPs, on the other hand, may be employed that connect one or more source end points to one or more destination end points, e.g., along a shared tree. These multipoint LSPs may be used in a manner similar to (and may complement) IP multicast, with packet replication at various LSRs of the shared tree, as will be understood by those skilled in the art. Notably, extensions to LDP are further described in the Internet Draft by Minei et al., entitled Label Distribution Protocol Extensions for Point-to-Multipoint and Multipoint-to-Multipoint Label Switched Paths <draft-ietf-mpls-ldp-p2mp-01>, dated June 2005 and in the Internet Draft by Wijnands et al., entitled Multicast Extensions for LDP <draft-wijnands-mpls-ldp-mcast-ext-00. txt>, dated March 2005, the contents of both of which are hereby incorporated by reference as though fully set forth herein. “Point-to-Multipoint” (P2MP) LSPs, for example, have one source end node to source traffic onto the P2MP LSP, and multiple destination end nodes to receive the traffic from the P2MP LSP. As mentioned above, the upstream source end (root) node may allocate an inner-label for sourced IP stream traffic, such that each of the destination end nodes may uniquely identify a received IP stream based on the upstream-allocated inner-label and forward the corresponding traffic without performing an IP lookup.
“Multipoint-to-Multipoint” (MP2MP) LSPs, on the other hand, may have multiple source end nodes to source traffic onto the MP2MP LSP, and multiple destination end nodes to receive the traffic from the MP2MP LSP. Thus, an MP2MP LSP utilizes a bi-directional tree, in which each end node may either source or receive traffic, e.g., for various IP streams. (For instance, a multicast group utilizing MP2MP LSPs may employ the (*,G) source-independent notation.) One problem associated with using upstream-allocated inner-labels with MP2MP LSPs, however, is that there may be more than one source for a particular group that is sourcing traffic for an IP stream onto the MP2MP LSP. According to the upstream-allocated inner-label technique, each upstream source of the MP2MP LSP may allocate its own inner-label, which may be different from other sources' inner-labels. Accordingly, any end node receiving traffic for the IP stream on the MP2MP LSP will be unable to use the inner-labels effectively since it does not know to which source the inner-label belongs, and, unfortunately, may be required to perform an inefficient IP lookup operation. There remains a need, therefore, to avoid IP lookup with MP2MP LSPs.